Криптосистема Сидельникова
Криптосистема Сидельникова (Мак-Элиса—Сидельникова) — криптографическая система с открытым ключом, основанная на криптосистеме McEliece. Была предложена математиком, академиком Академии криптографии РФ Владимиром Михайловичем Сидельниковым в 1994 году[1]. Сидельников предложил данную криптосистему, поскольку для системы McEliece к тому времени уже были найдены алгоритмы, взламывающие её за полиномиальное, либо субэкспоненциальное время работы[2].
Алгоритм, используемый в криптосистеме Сидельникова, основан на сложности декодирования кода Рида-Маллера[1]. Порождающая матрица такого кода имеет размеры [math]\displaystyle{ k \times n, }[/math] где
- [math]\displaystyle{ k = \sum_{k=0}^r C_m^k, n = 2^m }[/math]
При использовании кода Рида-Маллера можно выбирать ключи меньшего размера, чем в криптосистеме McEliece; а также добиться высокой скорости расшифровки, так как для данного кода существуют быстрые алгоритмы декодирования[2]. Более того, криптосистема Сидельникова, как и любая система, построенная на линейных кодах, не является уязвимой для атак, которые станут возможны с появлением квантового компьютера.
Реального применения данная криптосистема не нашла, так как, несмотря на некоторые улучшения по сравнению с системой McEliece, была взломана в 2007 году.
В некоторых источниках упоминается как криптосистема Мак-Элиса—Сидельникова.
Генерация ключа
Система Сидельникова, как и все асимметричные криптосистемы, использует открытый и закрытый ключи. Открытый ключ используется для шифрования сообщений и не является секретным. Закрытый ключ используется для расшифровки и должен быть известен только стороне, которой предназначаются зашифрованные сообщения. Задача владельца закрытого ключа заключается в том, чтобы замаскировать порождающую матрицу [math]\displaystyle{ G }[/math], зная которую, криптоаналитик сумеет восстановить исходное сообщение. Для этих целей используются матрицы [math]\displaystyle{ P }[/math] и [math]\displaystyle{ A }[/math], описанные далее в алгоритме. Вычисления всюду происходят в [math]\displaystyle{ k }[/math]-мерном подпространстве пространства [math]\displaystyle{ \mathbb{F}_2^n }[/math].
Процесс генерации ключей происходит следующим образом[1]:
- Выбирается код Рида-Маллера с определёнными параметрами [math]\displaystyle{ r }[/math] и [math]\displaystyle{ m }[/math] (где [math]\displaystyle{ r }[/math] - порядок кода, а [math]\displaystyle{ 2^m }[/math] - длина кодового слова).
- Генерируется случайная [math]\displaystyle{ n \times n }[/math] перестановочная матрица [math]\displaystyle{ P }[/math].
- Генерируется случайная невырожденная [math]\displaystyle{ k \times k }[/math] матрица [math]\displaystyle{ A }[/math].
- Вычисляется матрица [math]\displaystyle{ E = AGP }[/math].
- Матрица [math]\displaystyle{ E }[/math] и число исправляемых кодом ошибок [math]\displaystyle{ t }[/math] образуют открытый ключ, а матрицы [math]\displaystyle{ (A, G, P) }[/math] — закрытый ключ криптосистемы.
Шифрование
Для кодирования при помощи линейных кодов (в частности, при помощи кода Рида-Маллера), необходимо представить информационное сообщение [math]\displaystyle{ m }[/math] в виде последовательности из [math]\displaystyle{ 0 }[/math] и [math]\displaystyle{ 1 }[/math]. Эта битовая последовательность шифруется следующим образом[1]:
- Вычисляется вспомогательный вектор [math]\displaystyle{ \mathbf a = mE }[/math].
- Случайным образом генерируется вектор ошибок [math]\displaystyle{ \mathbf e }[/math] размерности [math]\displaystyle{ n }[/math], содержащий единицы не более чем в [math]\displaystyle{ t = 2^{m-r-1} - 1 }[/math] разрядах.
- Передаваемый шифртекст вычисляется путём сложения ранее вычисленных векторов [math]\displaystyle{ \mathbf b = \mathbf a + \mathbf e }[/math].
Расшифрование
Шифртекст, полученный по общедоступному каналу, представляет собой вектор [math]\displaystyle{ \mathbf b = mE + \mathbf e }[/math], где [math]\displaystyle{ m }[/math] - информационное сообщение. Для расшифровки криптограммы[2]:
- Вычисляется вектор [math]\displaystyle{ \mathbf b' = \mathbf bP^{-1} }[/math], являющийся вектором кода Рида-Маллера с порождающей матрицей [math]\displaystyle{ G }[/math], искаженный не более, чем в [math]\displaystyle{ t }[/math] разрядах. Строго говоря, вектор ошибок [math]\displaystyle{ \mathbf e }[/math] при таком подходе также умножается на матрицу [math]\displaystyle{ P^{-1} }[/math], но для алгоритма декодирования это не имеет значения, так как его вес при перестановках, очевидно, остается прежним.
- С помощью какого-либо алгоритма декодирования кода Рида-Маллера находится вектор [math]\displaystyle{ \mathbf a' }[/math], удовлетворяющий условию [math]\displaystyle{ \mathbf b' = \mathbf a'G + \mathbf e }[/math].
- Вычисляется информационное сообщение [math]\displaystyle{ m = \mathbf a'A^{-1} }[/math].
Атака на криптосистему
Сидельников в одной из своих статей показал несостоятельность криптосистемы McEliece на основе кодов Рида-Соломона, найдя способ взлома такой системы за полиномиальное время[3]. В связи с этим, а также, желая устранить некоторые недостатки системы McEliece, Сидельников предложил и описал криптосистему, построенную на кодах Рида-Маллера[1].
Несмотря на то что Сидельников считал свою криптосистему надежной, в 2007 году криптографы Л. Миндер и А. Шокроллахи изобрели весьма оригинальный способ взломать систему Сидельникова. В основе метода лежало утверждение о том, что [math]\displaystyle{ RM(0, m) \subset RM(1, m) \subset \ldots \subset RM(m, m) }[/math] для любого [math]\displaystyle{ m }[/math] (здесь мы подходим к коду, как к линейному пространству, натянутому на базис из кодовых векторов)[2].
Обозначим за [math]\displaystyle{ RM(r, m)^\delta }[/math] код Рида-Маллера после применения к нему оператора перестановки. Тогда, найдя каким-либо способом перестановочную матрицу, которая использовалась при генерации закрытого ключа, можно, вычислив матрицу [math]\displaystyle{ P^{-1} }[/math] (это получится сделать, так как для любой перестановочной матрицы существует обратная), найти матрицу [math]\displaystyle{ G^* = AG }[/math]; поскольку открытым ключом в системе Сидельникова является матрица [math]\displaystyle{ AGP }[/math], умножив которую на [math]\displaystyle{ P^{-1} }[/math], можно найти [math]\displaystyle{ G^* }[/math][2].
Остается лишь вычислить матрицу [math]\displaystyle{ A }[/math]. Для решения данной задачи матрицы [math]\displaystyle{ G^* }[/math] и [math]\displaystyle{ E }[/math] записываются рядом, и с помощью линейных преобразований строк матрица [math]\displaystyle{ G^* }[/math] приводится к матрице [math]\displaystyle{ G }[/math], которая для данного кода Рида-Маллера заранее известна. В итоге имеется цепочка преобразований [math]\displaystyle{ (G^*|E) \rightarrow (G|A^{-1}) }[/math], что следует из элементарых сведений о линейной алгебре. Вообще говоря, матрицу [math]\displaystyle{ A }[/math] можно и не искать, так как достаточно легко показать, что матрицы [math]\displaystyle{ AG }[/math] и [math]\displaystyle{ G }[/math] порождают один и тот же код Рида-Маллера[2].
Сущность атаки
Миндер и Шокроллахи в своей статье предложили следующий способ поиска перестановочной матрицы:
- Ищутся кодовые векторы кода [math]\displaystyle{ RM(r, m)^\delta }[/math], которые с очень большой вероятностью принадлежат коду [math]\displaystyle{ RM(r - 1, m)^\delta }[/math]. Находится достаточное количество таких векторов, чтобы построить базис пространства [math]\displaystyle{ RM(r - 1, m)^\delta }[/math]. Поиск базируется на утверждении о том, что код Рида-Маллера порядка [math]\displaystyle{ r }[/math] является подпространством того же кода порядка [math]\displaystyle{ r - 1 }[/math], а также на свойствах кодовых векторов с минимальным весом.
- Повторяется шаг 1 до получения кода [math]\displaystyle{ RM(1, m)^\delta }[/math].
- Переставляя определённым образом столбцы [math]\displaystyle{ RM(1, m)^\delta }[/math], возможно отыскать исходный код [math]\displaystyle{ RM(1, m) }[/math] с вероятностью более [math]\displaystyle{ 1/2 }[/math] (потребуется максимум 2 итерации для получения положительного результата)[2]. Иными словами, возможно найти оператор перестановки, использовавшийся для генерации закрытого ключа.
Временные оценки алгоритма взлома
При временном анализе алгоритма за входной параметр принимается число [math]\displaystyle{ n = 2^m }[/math], являющееся размерностью кодового слова. Порядок кода [math]\displaystyle{ r }[/math] полагается малым в сравнении с [math]\displaystyle{ m }[/math], так как код Рида-Маллера при больших порядках достаточно бесполезен в плане практического применения (в частности, число исправляемых им ошибок при увеличении [math]\displaystyle{ r }[/math], становится очень мало). Наиболее вычислительно сложной частью всего алгоритма является поиск кодовых слов с минимальным весом, так как все остальные операции выполняются за заведомо полиномиальное время[2].
Асимптотическая оценка сложности алгоритма: [math]\displaystyle{ O(poly(n))\cdot e^{O(poly(log(n)))} }[/math]. Для больших порядков кода [math]\displaystyle{ r }[/math] задача становится вычислительно сложной, так как существенно возрастает время, затрачиваемое на поиск кодовых слов с минимальным весом[2].
Экспериментальное время работы
Миндером и Шокроллахи была проведена серия экспериментов на компьютере с тактовой частотой 2,4 Ггц[2]. Результаты можно видеть в таблице:
| [math]\displaystyle{ r = 2 }[/math] | [math]\displaystyle{ r = 3 }[/math] | [math]\displaystyle{ r = 4 }[/math] | |
|---|---|---|---|
| [math]\displaystyle{ m = 5~(n = 32) }[/math] | [math]\displaystyle{ \lt 0{,}01c }[/math] | ||
| [math]\displaystyle{ m = 6~(n = 64) }[/math] | [math]\displaystyle{ \lt 0{,}01c }[/math] | ||
| [math]\displaystyle{ m = 7~(n = 128) }[/math] | [math]\displaystyle{ 0{,}02c }[/math] | [math]\displaystyle{ 5{,}261c }[/math] | |
| [math]\displaystyle{ m = 8~(n = 256) }[/math] | [math]\displaystyle{ 0{,}081c }[/math] | [math]\displaystyle{ 2{,}059c }[/math] | |
| [math]\displaystyle{ m = 9~(n = 512) }[/math] | [math]\displaystyle{ 0{,}0448c }[/math] | [math]\displaystyle{ 3{,}462c }[/math] | [math]\displaystyle{ 176{,}914c }[/math] |
| [math]\displaystyle{ m = 10~(n = 1024) }[/math] | [math]\displaystyle{ 2{,}46c }[/math] | [math]\displaystyle{ 26{,}6c }[/math] | [math]\displaystyle{ 82197{,}4c }[/math] |
| [math]\displaystyle{ m = 11~(n = 2048) }[/math] | [math]\displaystyle{ 18{,}34c }[/math] | [math]\displaystyle{ 1192{,}71c }[/math] | [math]\displaystyle{ - }[/math] |
Время работы при [math]\displaystyle{ r = 3, m = 7 }[/math] является результатом погрешности в реализации алгоритма.
Обобщенная система Сидельникова
Сидельников также предложил усиленный вариант своей криптосистемы с использованием [math]\displaystyle{ u }[/math] порождающих матриц. Иными словами, публичный ключ в такой системе рассчитывается как [math]\displaystyle{ |AG_1, AG_2\ldots, AG_u|P }[/math], где первый множитель - составная матрица размером [math]\displaystyle{ un \times k }[/math].
Миндер и Шокроллахи в своей статье показали, что взлом усовершенствованной таким образом криптосистемы по сложности не отличается от взлома криптосистемы с единственной порождающией матрицей, так как разбиение кода на блоки оказывается весьма простой задачей[2].